package com.wzh.test.graphic;

import javax.swing.plaf.synth.SynthOptionPaneUI;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 有七个村庄（A,B,C,D,E,F,G）
 * 互相连接
 *
 * 要求：如何修路保证各个村庄都能联通，并且总的修建公路总里程最短
 */
public class PrimDemo {
    public static void main(String[] args) {
        Graphic graphic = new Graphic(7);
        String[] arrVertex = {"A","B","C","D","E","F","G"};
        for(int i = 0; i < arrVertex.length;i++) {
            graphic.addVertex(arrVertex[i]);
        }
        graphic.addEdge("A","B",5);
        graphic.addEdge("A","C",7);
        graphic.addEdge("A","G",2);

        graphic.addEdge("B","D",9);
        graphic.addEdge("B","G",3);

        graphic.addEdge("C","E",8);

        graphic.addEdge("D","F",4);

        graphic.addEdge("E","F",5);
        graphic.addEdge("E","G",4);

        graphic.addEdge("F","G",6);

        List<String> resultVertexList = primCalc(graphic);
        for (String s : resultVertexList) {
            System.out.println(s);
        }

    }

    public static List<String> primCalc(Graphic graphic){
        //循环遍历每一个节点，每次找到不在minEdges中最小的边，放入minEdges中
        //结果放入一个list中
        List<String> resultVertexList = new ArrayList<>();
        int[][] resultEdges = new int[graphic.vertexList.size()][graphic.vertexList.size()];

        for(int i = 0; i < graphic.vertexList.size() - 1;i++){
            if(!resultVertexList.contains(graphic.vertexList.get(i))){
                resultVertexList.add(graphic.vertexList.get(i));
            }
            int minEdgeVertexIndex = getMinEdgeVertexIndex(graphic, resultEdges, i);
            if(minEdgeVertexIndex != -1){
                resultEdges[i][minEdgeVertexIndex] = 1;
                if(!resultVertexList.contains(graphic.vertexList.get(minEdgeVertexIndex))) {
                    resultVertexList.add(graphic.vertexList.get(minEdgeVertexIndex));
                }
            }
        }

        System.out.println("村庄连接图");
        for(int i = 0; i < resultEdges.length ;i++){
            System.out.println(Arrays.toString(resultEdges[i]));
        }
        return resultVertexList;
   }

   public static int getMinEdgeVertexIndex(Graphic graphic,int[][] resultEdges,int row){
        int minEdge = -1;
        int minEdgeVertexIndex = -1;
        for(int column = 0; column < graphic.vertexList.size();column++){
            if(graphic.edges[row][column] > 0 && resultEdges[column][row] == 0 && (minEdge == -1 || graphic.edges[row][column] < minEdge)){
                minEdge = graphic.edges[row][column];
                minEdgeVertexIndex = column;
            }
        }
       return minEdgeVertexIndex;
   }
}
